package com.saltlux.tdd.algorithm;

public class MergeSort {

	public void sort(Integer[] array) {
		sort(array, 0, array.length - 1);
	}
	
	private void sort(Integer[] array, int start, int end) {
		if(start == end) return;
		
		IndexFinder finder = new IndexFinder();
		int centerIndex = finder.findCenter(array, start, end);
		sort(array, start, centerIndex - 1);
		sort(array, centerIndex, end);
		merge(array, start, centerIndex - 1, centerIndex, end);
	}

	public void merge(Integer[] array, int startA, int endA, int startB,int endB) {
		int sumOfLength = (endA - startA + 1) + (endB - startB + 1);
		Integer[] newArray = new Integer[sumOfLength];

		int currentA = startA;
		int currentB = startB;

		for(int i=0; i<sumOfLength; i++) {
			if (currentA <= endA && (currentB > endB || array[currentA] < array[currentB])) {
				newArray[i] = array[currentA];
				currentA++;
			} else {
				newArray[i] = array[currentB];
				currentB++;
			}
		}

		int currentIndex = 0;
		for(int i=startA; i<=endA; i++) {
			array[i] = newArray[currentIndex];
			currentIndex++;
		}
		
		for(int i=startB; i<=endB; i++) {
			array[i] = newArray[currentIndex];
			currentIndex++;
		}
	}
}
